#include <iostream>
using namespace std;

int a[] = {1, 10, 100, 6, 7, 9, 5, 2, 47, 86, 4, 3};
const int LEN = sizeof(a) / sizeof(int);

int partition(int* A, int left, int right) {
    int x = A[right];
    int i = left - 1;

    for (int j = left; j < right; j++) {
        if (A[j] <= x) {
            i += 1;
            int t = A[i];
            A[i] = A[j];
            A[j] = t;
        }
    }

    int t = A[i+1];
    A[i+1] = A[right];
    A[right] = t;

    return i + 1;
}

void quicksort(int* A, int left, int right) {
    if (left >= right)
        return;

    int q = partition(A, left, right);
    quicksort(A, left, q-1);
    quicksort(A, q+1, right);
}

void print() {
    for (int i = 0; i < LEN; i++) {
        cout << a[i] << " ";
    }
    cout << endl;
}

int main() {
    quicksort(a, 0, LEN - 1);
    print();
    return 0;
}
